// Package day_12_dp 11-542
// @Title day_12_dp
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/7 10:05
// @Create  2021/9/7 10:05
package day_12_dp

func UpdateMatrix(mat [][]int) [][]int {
	n, m := len(mat), len(mat[0])
	dp := mat
	// 第一步从左上往右下进行一次搜索
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if mat[i][j] == 0 {
				dp[i][j] = 0
			} else {
				if j > 0 {
					dp[i][j] = min(dp[i][j], dp[i][j-1]) + 1
				}
				if i > 0 {
					dp[i][j] = min(dp[i][j], dp[i-1][j]) + 1
				}
			}
		}
	}
	// 第二步 从右下往左上进行一次DP搜索
	for i := n - 1; i >= 0; i-- {
		for j := m - 1; j >= 0; j-- {
			if mat[i][j] != 0 {
				if j < m-1 {
					dp[i][j] = min(dp[i][j], dp[i][j+1]+1)
				}
				if i < n-1 {
					dp[i][j] = min(dp[i][j], dp[i+1][j]+1)
				}
			}
		}
	}
	return dp
}
